Tags: #◇Computer Science #◇CSALGCM #◇Algorithms #◇Complexity Theory #◇Reviewer #◇Finals

---

CSALGCM Comprehensive Finals Reviewer

◇Overview

This reviewer synthesizes Algorithms and Advanced Complexity (CSALGCM). Subjects cover computational complexity analysis (Asymptotic notations $O, \Omega, \Theta$, recurrence relations via Master Theorem, Recursion Tree, and Substitution methods), Divide and Conquer paradigms (MergeSort, QuickSort, Closest Pair of Points, Strassen's Matrix Multiplication), Dynamic Programming (optimal substructure, overlapping subproblems, memoization vs tabulation: 0/1 Knapsack, Longest Common Subsequence, Matrix Chain Multiplication, Levenshtein Edit Distance), Greedy Algorithms (Greedy Choice Property, Exchange Arguments: Fractional Knapsack, Huffman Coding, Activity Selection, Job Sequencing), and Computational Intractability (Decision problems, P, NP, NP-Completeness, polynomial-time reductions $\le_P$, Cook-Levin theorem, 3-SAT, Vertex Cover, Independent Set, Hamiltonian Cycle, TSP).

---

◇1. Master Theorem Recurrence Matrix

For recurrences of the standard form $T(n) = a T(n/b) + f(n)$ with $a \ge 1, b > 1$:
Let $c_{\text{crit}} = \log_b(a)$.

---

◇2. Dynamic Programming Formulations

---

◇3. Complexity Classes & Reduction Hierarchy

• P: Problems solvable in deterministic polynomial time $O(n^k)$.
• NP: Decision problems verifiable by a deterministic Turing machine in polynomial time given a certificate.
• NP-Complete: $L \in \text{NP}$ and $\forall L' \in \text{NP}, L' \le_P L$.
• Reduction Rule: If $A \le_P B$ and $B \in \text{P} \implies A \in \text{P}$. If $A \le_P B$ and $A$ is NP-hard $\implies B$ is NP-hard!

---

◇4. High-Yield Exam Checklist

• In the Master Theorem, can you apply it if $b \le 1$ or $a < 1$? NO.
• What is the time complexity of the 0/1 Knapsack DP algorithm? Pseudo-polynomial $O(n W)$ (polynomial in $n$ and magnitude of $W$, but exponential in the number of bits of $W$).
• To prove a new problem $Y$ is NP-Complete, what must you reduce? Reduce a known NP-Complete problem $X$ to $Y$ ($X \le_P Y$), NOT $Y \to X$!
• Does Fractional Knapsack require dynamic programming? NO, it is solved greedily by sorting by value-to-weight ratio $v_i / w_i$ in $O(n \log n)$.
• What is the optimal prefix code length metric in Huffman coding? Weighted average path length $\sum f_i \cdot \text{length}(c_i)$.

---

◇References & Navigation

• Previous Topic: ◇CCDSALG, ◇CCDSTRU
• Next Topic: None
• Prerequisites: ◇Algorithms and Complexity, Master Theorem, DP, Greedy, NP-Completeness
• Cross-Curricular Connections: ◇CSINTSY